//maze2.cpp: �Թ���⣨��̬��ʾ�����
#include<stdio.h>
#include <windows.h>
//#include <iostream>
#include "SqStack.h"

#define MARK_FOOT 2			//�㼣���
#define MARK_IMPASSABLE 3	//����ͨ�����

//========================================================

Status Equal(PosType pos1, PosType pos2) {
 return (pos1.row == pos2.row) && (pos1.col == pos2.col); 
}//Equal

void gotoxy(int x, int y) {
 COORD pos = {x,y};
 HANDLE hOut = GetStdHandle(STD_OUTPUT_HANDLE);
 SetConsoleCursorPosition(hOut, pos);
}//gotoxy

void RowCol2XY(int row, int col, int &x, int &y) {
 x = 2 * col;
 y = row;
}//RowCol2XY

void Go2RowCol(int row, int col) {
 int x, y;
 RowCol2XY(row, col, x, y);
 gotoxy(x, y);
}//Go2RowCol

void Flash(int x, int y, char *s) {
 for (int i = 0; i < 3; i++) {
  gotoxy(x, y); printf(s);    _sleep(200);
  gotoxy(x, y); printf("  "); _sleep(200);
 }//end for
 gotoxy(x, y); printf(s);
}//Flash

void ShowStatus(int maze[][10], SElemType &e) {
 int x, y;
 
 RowCol2XY(e.seat.row, e.seat.col, x, y);
 if (maze[e.seat.row][e.seat.col] == MARK_IMPASSABLE)
  Flash(x, y, "��");
 else {
  switch (e.di) {
   case 1: Flash(x, y, "��"); break;
   case 2: Flash(x, y, "��"); break;
   case 3: Flash(x, y, "��"); break;
   case 4: Flash(x, y, "��"); break;
   //default : printf("  ");
  }//end switch
 }//end else
}//ShowStatus

//========================================================

//�ж�λ��pos�Ƿ��ͨ��
Status Pass(int maze[][10], PosType pos) {
 if (maze[pos.row][pos.col] == 0)
  return TRUE;     
 else
  return FALSE;  
}//Pass

//��λ��pos�����߹��㼣
void Foot(int maze[][10], PosType pos) {
 maze[pos.row][pos.col] = MARK_FOOT;
}//Foot

//��λ��pos�����߹��㼣
void SetImpassable(int maze[][10], PosType pos) {
 maze[pos.row][pos.col] = MARK_IMPASSABLE;
}//SetImpassable

//���ص�ǰλ��CurPos��di������ھ�λ��
PosType NextPos(PosType CurPos, int di) {
 PosType NewPos; 
 switch (di) {
  case 1: //��
   NewPos.row = CurPos.row;
   NewPos.col = CurPos.col + 1;
   break;
  case 2: //��
   NewPos.row = CurPos.row + 1;
   NewPos.col = CurPos.col;
   break;
  case 3: //��
   NewPos.row = CurPos.row;
   NewPos.col = CurPos.col - 1;
   break;
  case 4: //��
   NewPos.row = CurPos.row - 1;
   NewPos.col = CurPos.col;
   break;
 }//end switch
 return NewPos;
}//NextPos
 
//���Թ�maze���д����start������end��ͨ���������һ�������ջ��(��ջ�׵�ջ��)��
//������TRUE�����򷵻�FALSE
Status MazePath(int maze[][10], PosType start, PosType end, SqStack &S) {  
  PosType curpos;
  int curstep;
  SElemType e;

  InitStack(S);
  curpos = start;  //�趨"��ǰλ��"Ϊ"���λ��"
  curstep = 1;     //̽����һ��
  do {
   if (Pass(maze, curpos)) {//��ǰλ�ÿ�ͨ��������δ���ߵ�����ͨ����
    Foot(maze, curpos);		//�����㼣
    e.ord = curstep;	//·�����
	e.seat = curpos;	//ͨ����λ��
	e.di = 1;			//��һ�鷽��(��)
    Push(S, e);			//ͨ����e����·��
	/////////////////
	ShowStatus(maze, e);
	/////////////////
	if (Equal(curpos, end)) return TRUE;	//�����յ㣨���ڣ�
	curpos = NextPos(curpos, e.di);	//��һλ��(��)
	curstep++;						//̽����һ��
   } else {//��ǰλ�ò���ͨ�� //111
    if (!StackEmpty(S)) {//������·  //222
     Pop(S, e);	//�˻�һ��
     while (e.di == 4 && !StackEmpty(S)) {	//��e��4����������߹��һ�����·
      SetImpassable(maze, e.seat);			//��עe����ͨ��
	  //////////////////////
	  ShowStatus(maze, e);
	  //////////////////////
      Pop(S, e);							//�˻�һ��
     }//end while
     if (e.di < 4) {//��e�黹�з������  //333
      e.di++;		//����һ������
	  Push(S, e);	//��e����·��
      /////////////////
      ShowStatus(maze, e);
      /////////////////
      curpos = NextPos(e.seat, e.di); //��һλ��(��)
     }//end if 333
	}//end if 222
   }//end else 111
  } while (!StackEmpty(S) );
  return 0;
}//MazePath 

void ShowMaze(int maze[10][10]) {
 int row, col;
 for (row = 0; row < 10; row++) {
  for (col = 0; col < 10; col++) {
   if (maze[row][col] == 0)
    printf("��");
   else
    printf("��");
  }//end for col
  printf("\n");
 }//end for row
}//ShowMaze

void ShowPath(int maze[10][10], SqStack &S) {
 SElemType *p = S.base;
 while(p != S.top) {//��maze�м���·���ϵĿ鼰����
  maze[p->seat.row][p->seat.col] = 10 + p->di; //����+10�������롰ǽ(1)����MARK_IMPASSABLE����С��10�ı�ǣ�
  p++;
 }//end while

 int row, col;
 for (row = 0; row < 10; row++) {
  for (col = 0; col < 10; col++) {
   switch (maze[row][col]) {
    case 0: printf("��"); break;
    case 1: printf("��"); break;
    case 11: printf("��"); break;
    case 12: printf("��"); break;
    case 13: printf("��"); break;
    case 14: printf("��"); break;
	case MARK_IMPASSABLE: printf("��"); break;
    default : printf("  ");
   }//end switch
  }//end for col
  printf("\n");
 }//end for row
}//ShowPath

int main() {
 int maze[10][10] = {
					{1,1,1,1,1,1,1,1,1,1},
					{1,0,0,1,0,0,0,1,0,1},
					{1,0,0,1,0,0,0,1,0,1},
					{1,0,0,0,0,1,1,0,0,1},
					{1,0,1,1,1,0,0,0,0,1},
					{1,0,0,0,1,0,0,0,0,1},
					{1,0,1,0,0,0,1,0,0,1},
					{1,0,1,1,1,0,1,1,0,1},
					{1,1,0,0,0,0,0,0,0,1},
					{1,1,1,1,1,1,1,1,1,1}
					};
  SqStack S;
  PosType start,end;

  ShowMaze(maze); printf("\n");
  start.row = 1; start.col = 1;
  end.row = 8; end.col = 8;
  if (MazePath(maze, start, end, S)) {//1
   //ShowPath(maze, S);
   Go2RowCol(11,0);        }//end 1
  else
   printf("��ͨ·��\n");

  return 0;
}//main
/* ��������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������

��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������
��������������������

*/






